package com.liufei.class07;

import com.liufei.common.TreeNode;

import java.util.LinkedList;
import java.util.List;

// https://leetcode.cn/problems/path-sum-ii/
public class Code03_PathSum_II {

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        process(root, 0, targetSum, new LinkedList<>(), res);
        return res;
    }

    // preSum不需要动，因为是按照值传递的
    // path需要清理，因为是按照引用传递的
    public static void process(TreeNode root, int preSum, int targetSum, List<Integer> path, List<List<Integer>> res) {
        // 如果当前节点是空，那么他的上一个节点不一定是叶子节点，所以这里不能使用 root == null 作为范围条件
        if (root.left == null && root.right == null) {
            // 1. 是叶子节点
            if (root.val + preSum == targetSum) {
                path.add(root.val);
                res.add(new LinkedList<>(path));
                path.remove(path.size() - 1);
            }
            return;
        }
        // 2. 非叶子节点，继续往下走
        preSum += root.val;
        path.add(root.val);
        // 注意这里需要做空判断，不然上面判断叶子节点逻辑会报空指针
        if (root.left != null) {
            process(root.left, preSum, targetSum, path, res);
        }
        if (root.right != null) {
            process(root.right, preSum, targetSum, path, res);
        }
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));
        List<List<Integer>> lists = pathSum(root, 22);
        System.out.println(lists);
    }
}
